/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import mosdi.fa.Alphabet;

/** Space efficient implementation of an array of booleans. Binary operations
 *  are also supported. */
public class BitArray implements Comparable<BitArray>, Iterable<Boolean> {
	private long[] array;
	private int size;
	
	public BitArray(int size) {
		this.size=size;
		int n = size/64;
		if (size%64>0) ++n;
		array = new long[n];
	}
	
	/** Copy constructor. */
	public BitArray(BitArray ba) {
		this.size=ba.size;
		this.array=new long[ba.array.length];
		System.arraycopy(ba.array, 0, this.array, 0, ba.array.length);
	}
	
	/** Constructs BitArray from string over {0,1}, where last bit in the string
	 *  will become the bit at index 0 in the BitArray.
	 */
	public BitArray(String s) {
		size = s.length();
		int n = size/64;
		if (size%64>0) ++n;
		array = new long[n];
		Alphabet alphabet = new Alphabet("01");
		for (int i=0; i<array.length; ++i) {
			int j = Math.min(s.length()-1, (i+1)*64 - 1);
			long l = 0;
			while (true) {
				int c = alphabet.getIndex(s.charAt(s.length() - j -1));
				l = (l<<1) + c;
				if (j%64==0) break;
				j -= 1;
			}
			array[i] = l;
		}
	}
	
	public boolean get(int index) {
		if ((index<0) || (index>=size)) throw new IndexOutOfBoundsException();
		int n = index/64;
		int m = index%64;
		return ((array[n]>>>m)&1L)==1L?true:false;
	}
	
	public void set(int index, boolean value) {
		if ((index<0) || (index>=size)) throw new IndexOutOfBoundsException();
		int n = index/64;
		int m = index%64;
		if (value) {
			array[n]=array[n]|(1L<<m);
		} else {
			array[n]=array[n]&~(1L<<m);
		}
	}
	
	public void set(int index, int value) {
		if ((index<0) || (index>=size)) throw new IndexOutOfBoundsException();
		int n = index/64;
		int m = index%64;
		if (value!=0) {
			array[n]=array[n]|(1L<<m);
		} else {
			array[n]=array[n]&~(1L<<m);
		}
	}
	
	public int size() {return size;}

	public int compareTo(BitArray o) {
		if (o.size!=this.size) throw new IllegalArgumentException();
		for (int i=array.length-1; i>=0; --i) {
			if (array[i]<o.array[i]) return -1;
			if (array[i]>o.array[i]) return 1;
		}
		return 0;
	}

	private class BitArrayIterator implements Iterator<Boolean> {
		private int n;
		private long l;
		BitArrayIterator() {
			n=0;
			l=array[0];
		}
		public boolean hasNext() { return n<size; }
		public Boolean next() {
			if (n>=size) throw new NoSuchElementException();
			boolean result = ((l&1L)==1L);
			l=l>>>1;
			++n;
			if ((n%64==0)&&(n<size)) l=array[n/64];
			return result;
		}
		public void remove() { throw new UnsupportedOperationException(); }
	}
	
	public Iterator<Boolean> iterator() { return new BitArrayIterator(); }

	/** Shifts left by one position. */
	public void shiftLeft() {
		long carry=0;
		for (int i=0; i<array.length; ++i) {
			long newCarry=array[i]>>>63;
			array[i]=(array[i]<<1)|carry;
			carry=newCarry;
		}
		if (size%64>0) array[array.length-1]&=(1L<<(size%64))-1L;		
	}
	
	/** Shifts right by one position. */
	public void shiftRight() {
		long carry=0;
		for (int i=array.length-1; i>=0; --i) {
			long newCarry=(array[i]&1L)<<63;
			array[i]=(array[i]>>>1)|carry;
			carry=newCarry;
		}
	}
	
	/** Returns true if the set of one bits is a subset of the set of one bits of ba. */
	public boolean subsetOf(BitArray ba) {
		if (ba.size!=size) throw new IllegalArgumentException("Must have same sizes.");
		for (int i=0; i<array.length; ++i) {
			if ((array[i] & ba.array[i]) != array[i]) {
				return false;
			}
		}
		return true;
	}
	
	public void and(BitArray ba) {
		if (ba.size!=size) throw new IllegalArgumentException("Must have same sizes.");
		for (int i=0; i<array.length; ++i) array[i]&=ba.array[i];
	}
	
	public void or(BitArray ba) {
		if (ba.size!=size) throw new IllegalArgumentException("Must have same sizes.");
		for (int i=0; i<array.length; ++i) array[i]|=ba.array[i];
	}
	
	public void invert() {
		for (int i=0; i<array.length; ++i) array[i]=~array[i];
		if (size%64>0) array[array.length-1]&=(1L<<(size%64))-1L;
	}
	
	/** Flip one bit. */
	public void flip(int bitnr) {
		int i = bitnr/64;
		array[i]^=1<<(bitnr%64); 
	}
	
	public boolean allZero() {
		boolean result = true;
		for (int i=0; i<array.length; ++i) {
			if (array[i]!=0) {
				result = false;
				break;
			}
		}
		return result;
	}

	/** Returns true of all bits are zero after an AND with the given bitarray. */
	public boolean allZeroAfterAnd(BitArray ba) {
		if (ba.size!=size) throw new IllegalArgumentException("Must have same sizes.");
		for (int i=0; i<array.length; ++i) {
			if ((array[i] & ba.array[i])!=0) return false;
		}
		return true;
	}
	
	public int numberOfOnes() {
		int result = 0;
		for (int i=0; i<array.length; ++i) {
			long tmp = array[i];
			while (tmp!=0) {
				result+=1;
				tmp=tmp&(tmp-1);
			}
		}
		return result;
	}
	
	/** Returns a BitArray containing the contents of the given range. 
	 *  @param from Start of interval (inclusive).
	 *  @param to End of interval (exclusive).
	 */
	public BitArray copyOfSubarray(int from, int to) {
		if ((from<0) || (to>size)) throw new IndexOutOfBoundsException();
		if (from>to) throw new IllegalArgumentException("Negative interval.");
		int length = to-from;
		int shift = from%64;
		BitArray result = new BitArray(length);
		int n = from/64;
		for (int i=0; i<result.array.length; ++i) {
			result.array[i] = array[n]>>>shift;
			if ((shift>0) && (n+1<array.length)) {
				result.array[i] |= array[n+1]<<(64-shift);
			}
			n += 1;
		}
		return result;
	}
	
	/** Concatenates the given bit arrays into one large bit array. */
	public static BitArray join(List<BitArray> list) {
		int totalLength = 0;
		for (BitArray ba : list) totalLength += ba.size;
		BitArray result = new BitArray(totalLength);
		int n = 0;
		for (BitArray ba : list) {
			int m = 0;
			while (m!=ba.size) {
				// compute number of bits that can be copied in one operation
				int j = Math.min(64-m%64, 64-n%64); 
				j = Math.min(j, ba.size-m);
				result.array[n/64] |= (ba.array[m/64]>>>(m%64))<<(n%64);
				m += j;
				n += j;
			}
		}
		return result;
	}
	
	@Override
	public boolean equals(Object obj) {
		if (this==obj) return true;
		if ((obj==null) || (obj.getClass()!=this.getClass())) return false;
		BitArray ba = (BitArray)obj;
		if (ba.size!=size) return false;
		for (int i=0; i<array.length; ++i) {
			if (ba.array[i]!=array[i]) return false;
		}
		return true;
	}

	@Override
	public int hashCode() {
		long result=0;
		for (long i : array) {
			result^=i;
		}
		int lower=(int)result;
		int upper=(int)(result>>>32);
		return lower^upper;
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("(");
		for (int i=size-1; i>=0; --i) {
			int m=i/64;
			int n=i%64;
			sb.append(((array[m]>>>n)&1L)==1L?'1':'0');
		}
		sb.append(")");
		return sb.toString();
	}
}
